﻿#include <iostream>
#include "LinkedListNode.h"

// 使用6个指针
// < pivot的指针2个，一个指向头，一个指向尾
// = pivot的指针2个，一个指向头，一个指向尾
// > pivot的指针2个，一个指向头，一个指向尾
static LinkedListNode* partition(LinkedListNode* head, int pivot)
{
	auto cur = head;
	LinkedListNode* smallerNode = nullptr;
	LinkedListNode* equalNode = nullptr;
	LinkedListNode* largerNode = nullptr;

	LinkedListNode* smallerStartNode = nullptr;
	LinkedListNode* equalStartNode = nullptr;
	LinkedListNode* largerStartNode = nullptr;

	while (cur)
	{
		if (cur->value < pivot)
		{
			if (!smallerNode)
			{
				smallerNode = cur;
				smallerStartNode = smallerNode;
			}
			else
			{
				smallerNode->next = cur;
				smallerNode = smallerNode->next;
			}
		}
		else if (cur->value == pivot)
		{
			if (!equalNode)
			{
				equalNode = cur;
				equalStartNode = equalNode;
			}
			else
			{
				equalNode->next = cur;
				equalNode = equalNode->next;
			}
		}
		else
		{
			if (!largerNode)
			{
				largerNode = cur;
				largerStartNode = largerNode;
			}
			else
			{
				largerNode->next = cur;
				largerNode = largerNode->next;
			}
		}

		cur = cur->next;
	}

	if (smallerNode)
	{
		smallerNode->next = equalStartNode ? equalStartNode : largerStartNode;
	}

	if (equalNode)
	{
		equalNode->next = largerStartNode;
	}

	if (largerNode)
	{
		largerNode->next = nullptr;
	}

	if (!smallerStartNode && !equalStartNode)
	{
		return largerStartNode;
	}

	if (!smallerStartNode)
	{
		return equalStartNode;
	}

	return smallerStartNode;
}

// 将单向链表按某值划分成左边小、中间相等、右边大的形式
// [题目] 给定一个单链表的头节点head, 节点的值类型是整型，再给定一个整 数pivot。实现一个调整链表的函数，
// 将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右部分都是值大于pivot的节点。
// [进阶] 在实现原问题功能的基础上增加如下要求
// (1) 调整后所有小于pivot的节点之间的相对顺序和调整前一致
// (2) 调整后所有等于pivot的节点之间的相对顺序和调整前一致
// (3) 调整后所有大于pivot的节点之间的相对顺序和调整前一致
// (4) 时间复杂度达到O(N), 额外空间复杂度达到O(1)
int main_LeftSmall_CenterEqual_RightLarge()
{
	auto head = new LinkedListNode(5);
	head->next = new LinkedListNode(3);
	head->next->next = new LinkedListNode(2);
	head->next->next->next = new LinkedListNode(7);
	head->next->next->next->next = new LinkedListNode(5);
	head->next->next->next->next->next = new LinkedListNode(4);
	head->next->next->next->next->next->next = new LinkedListNode(9);
	printLinkedList(head);

	auto newHead = partition(head, 2);
	delLinkedListNode(newHead);
	return 0;
}